COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.device xgp
C00005 ENDMK
C⊗;
.device xgp
.font 1 "basl30" <<text>>
.font 2 "bdr30" <<sym>>
.font 3 "basi30" <<var>>
.font 4 "basb30" <<bold>>
.font 5 "sup"
.evenleftborder←oddleftborder←1100;
.page frame 52 high 79 wide;
.area text lines 1 to 51 chars 1 to 79;
.place text;
.TURN ON "←%";
.NOFILL
←COMPUTER SCIENCE DEPARTMENT
←STANFORD UNIVERSITY



←CS 206         COMPUTING WITH SYMBOLIC EXPRESSIONS        SPRING 1977
←PROBLEM SET 1

%1←Due April 14

Write LISP functions as follows:  Debug your programs at LOTS, and submit
both printed output and the functions written in external notation.
(Do your final output to a file and list the file).  Include the internal
notation definitions in the file.
You should add the external notation definitions (in some reasonable
approximation) to the file with the editor before you print it.



.FILL
.SKIP 2
1. %3foo u%1 is a list consisting of the atomic elements of the list %3u%1
followed by the non-atomic elements preserving order within each group.
Thus

	%3foo%1[(A (B C) A B (D E))] = (A A B (B C) (D E)))


2. Let a polynomial in %3x%1 be represented by a list of its coefficients
in order of ascending powers of %3x%1.  Thus %3x%53%3+x+5%1 is represented
by (5 1 0 1).  %3prod(u,v)%1 gives the product of the polynomials %3u%1
and %3v%1 in the same notation.


3. %3commons u%1 is a list of the sublists of the list %3u%1 that occur
more than once in %3u%1 each followed by a list of the locations where
it occurs.  The location of a sub expression is a list of A's and D's
such that starting a the beginning of

4. %3locations%2[%3e,u%2]%1 is a list of the locations of the occurences
of the expression %3e%1 as a subexpression of the expression %3u%1.  A
location is a list of A's and D's such that %3e%1 is reached by taking